#include <stdlib.h>

#include "../image.h"
#include "../../util/macros.h"

#define LABEL_INC 10;

inline static int _label_find(int x, int * Parent);
inline static void _label_union(int x1, int x2, int * Parent);

inline static int _label_find(int x, int * Parent) {

	while (Parent[x] != -1) x = Parent[x];
	return x;

}

inline static void _label_union(int x1, int x2, int * Parent) {
	x1 = _label_find(x1, Parent);
	x2 = _label_find(x2, Parent);
	if (x1 != x2) Parent[x2] = x1;
}

/**
 * 
 * @param Mat
 * @param Label
 * @param count
 */
void image_label(Matrix * Mat, Matrix ** Label, int * count) {

	/***************************************************************************
	 * This procedure is implemented based on work:
	 * 
	 *		Lifeng He, Yuyan Chao, Kenji Suzuki, and Kesheng Wu. 2009. 
	 *		Fast connected-component labeling. Pattern Recogn. 42, 9
	 *		(September 2009), 1977-1987. DOI=10.1016/j.patcog.2008.10.013
	 *		http://dx.doi.org/10.1016/j.patcog.2008.10.013
	 * 
	 **************************************************************************/

	double * mat;
	double * label;

	int rows, columns;
	long int msize;

	long int max_comp;

	int * Table;

	int r, c;
	long int _r, i;

	_verify(Mat);
	_verify(Label);

	rows = Mat->rows;
	columns = Mat->columns;
	msize = Mat->size;
	mat = Mat->data;

	if (*Label == NULL) (*Label) = matrix_new(rows, columns);
	label = (*Label)->data;

	max_comp = CEIL(rows / 2.0) *  CEIL(columns / 2.0);

	Table = (int *) calloc(max_comp, sizeof (int));
	for (i = 0; i < max_comp; i++) {
		Table[i] = -1;
	}

	{ /* Step 01: Forward raster scan ======================================= */
		double left;
		double top_left;
		double top;
		double top_right;

		double c1, c2, c3, c4;

		double LABEL = 1;

		double VB, VF;

		VB = 0;
		VF = 255;

		*count = 0;

		for (r = 1, _r = r * columns; r < rows - 1; r++, _r += columns) {
			for (c = 1; c < columns - 1; c++) {
				i = _r + c;

				if (mat[i] == VB) continue;

				left = label[i - 1];
				top = label[i - columns];
				top_left = label[ i - columns - 1];
				top_right = label[i - columns + 1];

				c1 = left;
				c2 = top_left;
				c3 = top;
				c4 = top_right;

				if (c3 != VB) label[i] = c3;
				else if (c1 != VB) {
					label[i] = c1;
					if (c4 != VB) _label_union(c4, c1, Table);
				} else if (c2 != VB) {
					label[i] = c2;
					if (c4 != VB) _label_union(c2, c4, Table);
				} else if (c4) label[i] = c4;
				else {
					// new label
					label[i] = LABEL;
					LABEL += 1;
					(*count)++;
				}
			}
		}
	}
	{ /* Step 01.5: Intermediate step to compress the parent table ========== */

		for (i = 0; i < max_comp; i++) {
			if (Table[i] == -1) continue;

			(*count)--;
			Table[i] = _label_find(i, Table);
		}

	}
	{ /* Step 02: Backward verification ===================================== */
		long int x;
		for (i = 0; i < msize; i++) {
			x = label[i];
			label[i] = _label_find(x, Table);
		}
	}

	free(Table);
}

void _select8(Image Gray, int x, int y, Image ** Sel, unsigned char px) {

	unsigned char * gray;
	unsigned char * sel;

	int rows;
	int columns;

	int i;

	rows = Gray.height;
	columns = Gray.width;

	if (x < 0 || x >= columns) return;
	if (y < 0 || y >= rows) return;

	_verify(Sel);
	if (Sel) if (*Sel == NULL) (*Sel) = image_new(Gray.width, Gray.height, IMAGE_PALETTE_GRAY);


	gray = Gray.data;
	sel = (*Sel)->data;

	i = y * columns + x;

	if (sel[i] > 0) {
		// pixel just visited
		return;
	}

	if (gray[i] == 0) {
		// not connected pixel
		//sel[i] = 100; // Mark border
		return;
	}



	sel[i] = px;

	// left pixel
	_select8(Gray, x - 1, y, Sel, px);

	// right pixel
	_select8(Gray, x + 1, y, Sel, px);

	// top pixel
	_select8(Gray, x, y - 1, Sel, px);

	// bottom pixel
	_select8(Gray, x, y + 1, Sel, px);

	// top left
	_select8(Gray, x - 1, y - 1, Sel, px);

	// top right
	_select8(Gray, x + 1, y - 1, Sel, px);
	// bottom left
	_select8(Gray, x - 1, y + 1, Sel, px);
	// bottom right
	_select8(Gray, x + 1, y + 1, Sel, px);


}

void _select4(Image Gray, int x, int y, Image ** Sel, unsigned char px) {

	unsigned char * gray;
	unsigned char * sel;

	int rows;
	int columns;

	int i;

	rows = Gray.height;
	columns = Gray.width;

	if (x < 0 || x >= columns) return;
	if (y < 0 || y >= rows) return;

	_verify(Sel);
	if (Sel) if (*Sel == NULL) (*Sel) = image_new(Gray.width, Gray.height, IMAGE_PALETTE_GRAY);


	gray = Gray.data;
	sel = (*Sel)->data;

	i = y * columns + x;

	if (sel[i] > 0) {
		// pixel just visited
		return;
	}

	if (gray[i] == 0) {
		// not connected pixel
		//sel[i] = 100; // Mark border
		return;
	}



	sel[i] = px;

	// left pixel
	_select4(Gray, x - 1, y, Sel, px);

	// right pixel
	_select4(Gray, x + 1, y, Sel, px);

	// top pixel
	_select4(Gray, x, y - 1, Sel, px);

	// bottom pixel
	_select4(Gray, x, y + 1, Sel, px);

}

void image_label8(Image Gray, Image ** Label, int * count) {

	unsigned char * gray;
	unsigned char * label;

	int rows;
	int columns;

	int r, c, _r, i;
	int up, left;

	unsigned char LABEL;

	_verify(Label);
	if (Label) if (*Label == NULL) (*Label) = image_new(Gray.width, Gray.height, IMAGE_PALETTE_GRAY);

	gray = Gray.data;
	rows = Gray.height;
	columns = Gray.width;

	label = (*Label)->data;

	LABEL = 0;
	(*count) = 0;

	// Step 01:
	for (r = 0, _r = r * columns; r < rows; r++, _r += columns) {
		for (c = 0; c < columns; c++) {
			i = _r + c;

			if (gray[i] == 0) continue;

			if (label[i] > 0) continue;

			up = i - columns;
			left = i - 1;

			LABEL += 50;
			(*count)++;

			_select8(Gray, c, r, Label, LABEL);

		}
	}
}

void image_label4(Image Gray, Image ** Label, int * count) {

	unsigned char * gray;
	unsigned char * label;

	int rows;
	int columns;

	int r, c, _r, i;
	int up, left;

	unsigned char LABEL;

	_verify(Label);
	if (Label) if (*Label == NULL) (*Label) = image_new(Gray.width, Gray.height, IMAGE_PALETTE_GRAY);

	gray = Gray.data;
	rows = Gray.height;
	columns = Gray.width;

	label = (*Label)->data;

	LABEL = 0;
	(*count) = 0;

	// Step 01:
	for (r = 0, _r = r * columns; r < rows; r++, _r += columns) {
		for (c = 0; c < columns; c++) {
			i = _r + c;

			if (gray[i] == 0) continue;

			if (label[i] > 0) continue;

			up = i - columns;
			left = i - 1;

			LABEL += 50;
			(*count)++;

			_select4(Gray, c, r, Label, LABEL);

		}
	}
}

